#include "glSimple.c"
#include "voronoi.h"
#include <vector>
#include <string>
#include <sstream>
priority_queue<point,  vector<point>,  gt> points; // site events
priority_queue<event*, vector<event*>, gt> events; // circle events

using std::vector;
vector<point> pointList;
int oldsiz = 0;

using std::stringstream;
using std::string;

int fps = 0;
float time = 0;
int frames = 0;
int oldTime = 0;
int grabi = -1;

int neighbours[100][100];

int getClosest()
{
      float mind = 1e32;
      int closest = -1;
      for(int i=0; i<pointList.size(); i++)
      {
        point p = pointList[i];
        float dist = (mousx-p.x)*(mousx-p.x) + (mousy-p.y)*(mousy-p.y);
        if( dist < mind )
        {
          mind = dist;
          closest = i;
        }
      }
      
      if( mind < 8*8 )
      {
        glColor3ub(255,255,255);
        drawSph( pointList[closest].x, pointList[closest].y, -8 );
        return closest;
      }
      return -1;
}

void init()
{
}

// also draw to coords.
void box(float x, float y, float w, float h)
{
    moveTo(x,y);
    lineTo(x+w,y);
    lineTo(x+w,y+h);
    lineTo(x,y+h);
    lineTo(x,y-1);
}

void draw(void)
{
    time = klock();
    
    
    if(time > oldTime)
    {
        oldTime = time + 1;
        fps = frames;
        frames = 0;
    }
    
  //glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
    glClear(GL_COLOR_BUFFER_BIT);
    glColor3ub(255,255,0);

    
  
    if( grabi != -1 )
    {
      point p = pointList[grabi];
      p.x = mousx; p.y = mousy;
      pointList[grabi] = p;
    }
    
    int closest = getClosest();
    if(bstatus == 1 && closest != -1 && grabi == -1)
    {
      grabi = closest;
      point p = pointList[closest];
      p.x = mousx; p.y = mousy;
      // Keep track of bounding box size.
      if (p.x < X0) X0 = p.x;
      if (p.y < Y0) Y0 = p.y;
      if (p.x > X1) X1 = p.x;
      if (p.y > Y1) Y1 = p.y;
      pointList[closest] = p;
    }
    else if(bstatus == 1 && grabi == -1)
    {
      bstatus = bstatus & ~1;

      point p;
      p.x = mousx;
      p.y = mousy;
      
      pointList.push_back(p);
    }
    else if(bstatus == 0)
    {
      grabi = -1;
    }
    
    if(bstatus == 2)
    {
      bstatus = bstatus & ~2;
      pointList.clear();
      output.clear();
    }
    
    if( pointList.size() > 2)
    {
      glColor3ub(0,23,128);
      box(X0,Y0, (X1-X0), (Y1-Y0) );
    }
    
    if( pointList.size() >= 3)
    {

    
      oldsiz = pointList.size();
      output.clear();
      
      while( !points.empty() )
        points.pop();
        
      while( !events.empty() )
        events.pop();  
        
      root = 0;
      for(int i=0; i<pointList.size(); i++)
      {
        points.push(pointList[i]);
      }
      
      
      // Process the queues; select the top element with smaller x coordinate.
      while (!points.empty())
        if (!events.empty() && events.top()->x <= points.top().x)
          process_event();
        else
          process_point();

      // After all points are processed, do the remaining circle events.
      while (!events.empty())
        process_event();
        
      finish_edges(); // Clean up dangling edges.
    }
    
    glColor3ub(0,0,255);
    for(int i=0; i<pointList.size(); i++)
    {
      point p = pointList[i];
      drawSph( p.x, p.y, -3 );
      if( i==0 )
      {
        X0 = p.x; Y0 = p.y; X1 = p.x; Y1 = p.y;
      }
      // Keep track of bounding box size.
      if (p.x < X0) X0 = p.x;
      if (p.y < Y0) Y0 = p.y;
      if (p.x > X1) X1 = p.x;
      if (p.y > Y1) Y1 = p.y;
    }
    /* // expand box
    float s = 10;
    X0 -= s;
    Y0 -= s;
    X1 += s;
    Y1 += s;
    */
    
    if( keystatus['v'] )
    {
      display_voronoi();
    }
    if( keystatus['d'] )
    {
      display_delaunay();
    }
    
    
    // duplicate evaldraw and processing?
    //  dl processing
    glColor3ub(255,0,0);
    
    moveTo(10,15*1);
    glPrintf("points %i", pointList.size());
    moveTo(10,15*2);
    glPrintf("time %.6f", time);
    moveTo(10,15*3);
    glPrintf("fps %i", fps);
    moveTo(10,15*4);
    glPrintf("bstatus %x", bstatus);
    
    stringstream ss;
    
    ss << ios_base::hex << bstatus;
    char mystr[100];
    sprintf(mystr, ss.str().c_str() );
    moveTo(10,100);
    glPrintf("String: %s", mystr);
    

    
    glutSwapBuffers();
    numframes++;
    frames++;
}



void process_point()
{
   // Get the next point from the queue.
   point p = points.top();
   points.pop();

   // Add a new arc to the parabolic front.
   front_insert(p);
}

void process_event()
{
   // Get the next event from the queue.
   event *e = events.top();
   events.pop();

   if (e->valid) {
      // Start a new edge.
      seg *s = new seg(e->p);

      // Remove the associated arc from the front.
      arc *a = e->a;
      if (a->prev) {
         a->prev->next = a->next;
         a->prev->s1 = s;
      }
      if (a->next) {
         a->next->prev = a->prev;
         a->next->s0 = s;
      }

      // Finish the edges before and after a.
      if (a->s0) a->s0->finish(e->p);
      if (a->s1) a->s1->finish(e->p);

      // Recheck circle events on either side of p:
      if (a->prev) check_circle_event(a->prev, e->x);
      if (a->next) check_circle_event(a->next, e->x);
   }
   delete e;
}

void front_insert(point p)
{
   if (!root) {
      root = new arc(p);
      return;
   }

   // Find the current arc(s) at height p.y (if there are any).
   for (arc *i = root; i; i = i->next) {
      point z, zz;
      if (intersect(p,i,&z)) {
         // New parabola intersects arc i.  If necessary, duplicate i.
         if (i->next && !intersect(p,i->next, &zz)) {
            i->next->prev = new arc(i->p,i,i->next);
            i->next = i->next->prev;
         }
         else i->next = new arc(i->p,i);
         i->next->s1 = i->s1;

         // Add p between i and i->next.
         i->next->prev = new arc(p,i,i->next);
         i->next = i->next->prev;

         i = i->next; // Now i points to the new arc.

         // Add new half-edges connected to i's endpoints.
         i->prev->s1 = i->s0 = new seg(z);
         i->next->s0 = i->s1 = new seg(z);

         // Check for new circle events around the new arc:
         check_circle_event(i, p.x);
         check_circle_event(i->prev, p.x);
         check_circle_event(i->next, p.x);

         return;
      }
   }

   // Special case: If p never intersects an arc, append it to the list.
   arc *i;
   for (i = root; i->next; i=i->next) ; // Find the last node.

   i->next = new arc(p,i);
   // Insert segment between p and i
   point start;
   start.x = X0;
   start.y = (i->next->p.y + i->p.y) / 2;
   i->s1 = i->next->s0 = new seg(start);
}

// Look for a new circle event for arc i.
void check_circle_event(arc *i, double x0)
{
   // Invalidate any old event.
   if (i->e && i->e->x != x0)
      i->e->valid = false;
   i->e = NULL;

   if (!i->prev || !i->next)
      return;

   double x;
   point o;

   if (circle(i->prev->p, i->p, i->next->p, &x,&o) && x > x0) {
      // Create new event.
      i->e = new event(x, o, i);
      events.push(i->e);
   }
}

// Find the rightmost point on the circle through a,b,c.
bool circle(point a, point b, point c, double *x, point *o)
{
   // Check that bc is a "right turn" from ab.
   if ((b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) > 0)
      return false;

   // Algorithm from O'Rourke 2ed p. 189.
   double A = b.x - a.x,  B = b.y - a.y,
          C = c.x - a.x,  D = c.y - a.y,
          E = A*(a.x+b.x) + B*(a.y+b.y),
          F = C*(a.x+c.x) + D*(a.y+c.y),
          G = 2*(A*(c.y-b.y) - B*(c.x-b.x));

   if (G == 0) return false;  // Points are co-linear.

   // Point o is the center of the circle.
   o->x = (D*E-B*F)/G;
   o->y = (A*F-C*E)/G;

   // o.x plus radius equals max x coordinate.
   *x = o->x + sqrt( pow(a.x - o->x, 2) + pow(a.y - o->y, 2) );
   return true;
}

// Will a new parabola at point p intersect with arc i?
bool intersect(point p, arc *i, point *res)
{
   if (i->p.x == p.x) return false;

   double a,b;
   if (i->prev) // Get the intersection of i->prev, i.
      a = intersection(i->prev->p, i->p, p.x).y;
   if (i->next) // Get the intersection of i->next, i.
      b = intersection(i->p, i->next->p, p.x).y;

   if ((!i->prev || a <= p.y) && (!i->next || p.y <= b)) {
      res->y = p.y;

      // Plug it back into the parabola equation.
      res->x = (i->p.x*i->p.x + (i->p.y-res->y)*(i->p.y-res->y) - p.x*p.x)
                / (2*i->p.x - 2*p.x);

      return true;
   }
   return false;
}

// Where do two parabolas intersect?
point intersection(point p0, point p1, double l)
{
   point res, p = p0;

   if (p0.x == p1.x)
      res.y = (p0.y + p1.y) / 2;
   else if (p1.x == l)
      res.y = p1.y;
   else if (p0.x == l) {
      res.y = p0.y;
      p = p1;
   } else {
      // Use the quadratic formula.
      double z0 = 2*(p0.x - l);
      double z1 = 2*(p1.x - l);

      double a = 1/z0 - 1/z1;
      double b = -2*(p0.y/z0 - p1.y/z1);
      double c = (p0.y*p0.y + p0.x*p0.x - l*l)/z0
               - (p1.y*p1.y + p1.x*p1.x - l*l)/z1;

      res.y = ( -b - sqrt(b*b - 4*a*c) ) / (2*a);
   }
   // Plug back into one of the parabola equations.
   res.x = (p.x*p.x + (p.y-res.y)*(p.y-res.y) - l*l)/(2*p.x-2*l);
   return res;
}

void finish_edges()
{
   // Advance the sweep line so no parabolas can cross the bounding box.
   double l = X1 + (X1-X0) + (Y1-Y0);

   // Extend each remaining segment to the new parabola intersections.
   for (arc *i = root; i->next; i = i->next)
      if (i->s1)
         i->s1->finish(intersection(i->p, i->next->p, l*2));
}

void display_voronoi()
{
   // Bounding box coordinates.
   //cout << X0 << " "<< X1 << " " << Y0 << " " << Y1 << endl;

   // Each output segment in four-column format.
   vector<seg*>::iterator i;
   for (i = output.begin(); i != output.end(); i++) {
      point p0 = (*i)->start;
      point p1 = (*i)->end;
      drawSph(p0.x, p0.y,3); drawSph(p1.x, p1.y,3);
      moveTo(p0.x, p0.y);
      lineTo(p1.x, p1.y);
   }
}

void display_delaunay()
{
  if(pointList.size() > 99) return;
  
  //neighbours[0][0] = 0;
  
  glColor3ub(128,128,0);
  drawSph(0,0,5);
  for(int i=0; i!=pointList.size(); i++)
  {
    moveTo( pointList[i].x, pointList[i].y );
    for(int j=0; j!=pointList.size(); j++)
    {
      if(i==j) continue;
      //if( neighbours[i][j] ) lineto( lineTo( pointList[j].x, pointList[j].y );
    }
    /*
    for(int j=0; j!=pointList.size(); j++)
    {
      if( i==j ) continue;
      lineTo( pointList[j].x, pointList[j].y );
    }
    */
    
    
   vector<seg*>::iterator j;
   for (j = output.begin(); j != output.end(); j++) {
      point p0 = (*j)->start;
      point p1 = (*j)->end;
      
      //moveTo(p0.x, p0.y);
      if( fabs( pointList[i].x-p0.x ) < 1e-7 )
      {
        if( fabs( pointList[i].y-p0.y ) < 1e-7 ) lineTo(p1.x, p1.y);
      }
      
   }
   
  }
  
}
